package learn.algorithm.sort;

import learn.algorithm.utils.GeneralUtils;

import java.lang.reflect.Constructor;
import java.util.*;

interface SortStrategy {
    void sort(int[] arr);
}

class BubbleSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        int n = arr.length;
        boolean swapped = false;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }
}

class InsertionSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i - 1;
            int key = arr[i];
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

class SelectionSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] <= arr[minIndex]) {
                    minIndex = j;
                }
            }
            GeneralUtils.swap(arr, i, minIndex);
        }
    }
}

class MergeSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    private void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= right) {
            temp[k++] = arr[j++];
        }

        System.arraycopy(temp, 0, arr, left, temp.length);
    }
}

class QuickSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 获取分区点
            int pivotIndex = partition(arr, left, right);
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // 选择最右边的元素作为基准值
        int i = left; // 记录小于基准值的元素的位置,一开始指向最左边的元素
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                GeneralUtils.swap(arr, i, j);
                i++;
            }
        }
        GeneralUtils.swap(arr, i, right);
        return i;
    }

}

class HeapSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        int n = arr.length;
        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 交换堆顶元素和最后一个元素
        for (int i = n - 1; i > 0; i--) {
            GeneralUtils.swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    private void heapify(int[] arr, int n, int index) {
        int largest = index; // 初始化最大元素为根节点
        int left = 2 * index + 1; // 左子节点
        int right = 2 * index + 2; // 右子节点

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // 如果最大元素不是根节点，则交换它们，并继续调整子树
        if (largest != index) {
            GeneralUtils.swap(arr, index, largest);
            heapify(arr, n, largest);
        }
    }
}

class RadixSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt(); // 获取数组中的最大值,以确定需要进行多少轮排序
        int exp = 1; // 基数，从个位开始
        for (; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    private void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 计数数组

        // 统计每个元素的出现次数
        for (int j : arr) {
            count[(j / exp) % 10]++;
        }

        // 计算每个元素在输出数组中的起始位置
        // 采取向前累加的方式，获取元素个数确定最终位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 将元素按照计数数组的位置放入输出数组中
        // 从后往前遍历，保证排序的稳定性。因为当两元素相同时，后面的元素仍然排在后面
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i]; // 这里-1是因为数组下标从0开始，而count数组里面的值指的是元素个数
            count[digit]--;
        }

        // 将输出数组复制回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }
}

class CountingSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt(); // 获取数组中的最大值,以确定需要进行多少轮排序
        int min = Arrays.stream(arr).min().getAsInt(); // 获取数组中的最小值,以确定需要进行多少轮排序
        int range = max - min + 1; // 计算取值范围
        int[] count = new int[range]; // 计数数组
        int[] output = new int[arr.length]; // 输出数组
        // 统计每个元素的出现次数
        for (int j : arr) {
            count[j - min]++;
        }
        // 计算每个元素在输出数组中的起始位置
        // 采取向前累加的方式，获取元素个数确定最终位置
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }
        // 将元素按照计数数组的位置放入输出数组中
        // 从后往前遍历，保证排序的稳定性。因为当两元素相同时，后面的元素仍然排在后面
        for (int i = arr.length - 1; i >= 0; i--) {
            int digit = arr[i] - min;
            output[count[digit] - 1] = arr[i]; // 这里-1是因为数组下标从0开始，而count数组里面的值指的是元素个数
            count[digit]--;
        }
        // 将输出数组复制回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
    }

    // 另一种更直接的算法，用偏移量和计数数组重构结果数组
    // 这种方法没有体现算法的稳定性
    private void countingSort(int[] arr, int min, int max) {
        int range = max - min + 1; // 计算取值范围
        int[] count = new int[range]; // 计数数组
        int[] output = new int[arr.length]; // 输出数组
        // 统计每个元素的出现次数
        for (int j : arr) {
            count[j - min]++;
        }
        int index = 0;
        for (int i = 0; i < range; i++) {
            while (count[i] > 0) {
                arr[index++] = i + min; // 重构结果数组
                count[i]--;
            }
        }
    }

    // 测试方法二
    public void test() {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr, 1, 8);
        System.out.println(Arrays.toString(arr));
    }
}

class BucketSort implements SortStrategy {

    private static final int BUCKET_SIZE = 10; // 桶的大小,根据数据范围调整。这里的测试范围为0-100

    @Override
    public void sort(int[] arr) {
        List<Integer>[] buckets = new ArrayList[BUCKET_SIZE]; // 桶数组

        // 初始化桶
        for (int i = 0; i < BUCKET_SIZE; i++) {
            buckets[i] = new ArrayList<>();
        }
        // 将元素放入桶中
        for (int i : arr) {
            int index = i / BUCKET_SIZE;
            // 边界需要特殊处理，这里0-100 可能取到100 会越界
            if (index == BUCKET_SIZE) {
                index--;
            }
            buckets[index].add(i);
        }
        // 对每个桶进行排序
        for (int i = 0; i < BUCKET_SIZE; i++) {
            Collections.sort(buckets[i]);
        }
        // 将元素从桶中取出
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int i : bucket) {
                arr[index++] = i;
            }
        }
    }
}

class ShellSort implements SortStrategy {
    @Override
    public void sort(int[] arr) {
        int n = arr.length;
        int gap = n / 2; // 初始步长
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > key) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = key;
            }
            gap = gap / 2;
        }
    }
}

public class SortSummary {
    private SortStrategy sortStrategy;
    private static final String PACKAGE_NAME = "learn.algorithm.sort.";
    private static final String[] SORT_CLASS_NAMES = {"BubbleSort", "InsertionSort", "SelectionSort",
            "MergeSort", "QuickSort", "HeapSort", "RadixSort", "CountingSort", "BucketSort", "ShellSort"};

    public SortSummary() {
    }

    public SortSummary(SortStrategy sortStrategy) {
        this.sortStrategy = sortStrategy;
    }

    public void setSortStrategy(SortStrategy sortStrategy) {
        this.sortStrategy = sortStrategy;
    }

    public void sortFunction(int n, int min, int max) {
        int[] arr = GeneralUtils.generateRandomArray(n, min, max);
        printTitle();
        System.out.print("Original Array: ");
        GeneralUtils.printArray(arr);
        sortStrategy.sort(arr);
        System.out.print("Sorted Array: ");
        GeneralUtils.printArray(arr);
        printTail();
    }

    public void printTitle() {
        String strategyName = sortStrategy.getClass().getName();
        System.out.println("Sort Strategy: " + strategyName.substring(strategyName.lastIndexOf(".") + 1));
    }

    public void printTail() {
        System.out.println("----------------------------------------");
    }

    public static void main(String[] args) {
        SortSummary sortSummary = new SortSummary();
        String sortName = "";
        for (int i = 0; i < SORT_CLASS_NAMES.length

                ; i++) {
            sortName = PACKAGE_NAME + SORT_CLASS_NAMES[i];
            SortStrategy sortStrategy = SortStrategyCache.getSortStrategy(sortName);
            sortSummary.setSortStrategy(sortStrategy);
            sortSummary.sortFunction(10, 0, 100);
        }
    }
}

class SortStrategyCache {
    private static Map<String, SortStrategy> cache = new HashMap<>();

    public static SortStrategy getSortStrategy(String sortName) {
        cache.putIfAbsent(sortName, createSortStrategy(sortName));
        return cache.get(sortName);
    }

    private static SortStrategy createSortStrategy(String sortName) {
        // 根据排序名称创建相应的排序策略对象
        try {
            Class<?> clazz = Class.forName(sortName);
            return (SortStrategy) clazz.newInstance();
        } catch (Exception e) {
            e.printStackTrace();
            throw new RuntimeException("Failed to create sort strategy: " + sortName);
        }
    }
}
